package 二叉树;

import com.sun.source.tree.Tree;

import java.util.ArrayDeque;

public class 翻转二叉树 {
    public class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    class Solution{
        //DFS-递归
        //在这里中序是不行的，因为先左孩子交换后，再根孩子交换（做完后，右孩子已经变成了原来的左孩子），
        // 再右孩子交换孩子（此时其实是对原来的左孩子做交换） 最后就等于没换
        public TreeNode invertTree(TreeNode root){
            if (root==null) return null;
          invertTree(root.left);
          invertTree(root.right);
            swapChildren(root);
          return root;

        }
        public void swapChildren(TreeNode root){
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
        }
    }

    //BFS 层序遍历
    class Solution2{
        public TreeNode inverTree(TreeNode root){
            if (root == null)return null;
            ArrayDeque<TreeNode> deque = new ArrayDeque<>();
            deque.offer(root);
            while (!deque.isEmpty()) {
                int size = deque.size();
                while (size-- > 0) {
                    TreeNode poll = deque.poll();
                    swap(poll);
                    if (poll.left != null) deque.offer(poll.left);
                    if (poll.right != null) deque.offer(poll.right);
                }
            }
            return root;
        }
        public void swap(TreeNode root){
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
        }
    }
}
